#encoding: utf-8

import camino
from constants import *


class Flujo():
    #Tabla de flujos (lo que mande). Lo construimos como un diccionario de
    #capacidades sobrantes.
    #Sería de la forma {(lado1: {lado2: capacidad sobrante}}
    def __init__(self, matriz):
        self.flujo_max = 0
        self.nroincremento = 0
        self.lados = matriz  # la matriz debe ser la tabla de capacidades

    def capSobrante(self, x, y):
        """Devuelve la capacidad sobrante del lado xy"""
        return self.lados[x][y]

    def aumentar(self, camino):
        """Aumenta el flujo según el camino dado.

        >>> matriz = {0:{2:10, 3:10}, \
            2:{4:10}, 3:{4:20, 5:20}, \
            4:{1:10}, 5:{1:20}}
        >>> f = Flujo(matriz)
        >>> camino1 = camino.Camino_aumentante()
        >>> camino1.add(3, 10, FORW)
        >>> camino1.add(2, 10, FORW)
        >>> camino1.quitar()
        >>> camino1.add(4, 10, FORW)
        >>> camino1.add(5, 20, FORW)
        >>> camino1.quitar()
        >>> camino1.quitar()
        >>> camino1.add(1, 20, FORW)
        >>> f.aumentar(camino1)
        >>> f.flujo_max
        10
        >>> f.lados
        {0: {2: 10, 3: 0}, 2: {4: 10}, 3: {4: 10, 5: 20}, 4: {1: 0}, \
            5: {1: 20}}
        >>> camino2 = camino.Camino_aumentante()
        >>> camino2.add(2, 10, FORW)
        >>> camino2.quitar()
        >>> camino2.add(4, 10, FORW)
        >>> camino2.quitar()
        >>> camino2.add(3, 10, BACK)
        >>> camino2.quitar()
        >>> camino2.add(5, 20, FORW)
        >>> camino2.quitar()
        >>> camino2.add(1, 20, FORW)
        >>> camino2.camino_de_ancestros()
        [1, 5, 3, 4, 2, 0]
        >>> f.aumentar(camino2)
        >>> f.flujo_max
        20
        >>> f.lados
        {0: {2: 0, 3: 0}, 2: {4: 0}, 3: {4: 20, 5: 10}, 4: {1: 0}, 5: {1: 10}}
        """
        # Voy desde atrás hacia adelante. Usamos las posiciones en la cola
        # así es más simple.
        e = camino.camino_valor()  # valor del flujo del camino aumentante.
        self.nroincremento += 1
        camino_lista = camino.camino_de_ancestros()
        i = 0  # recorro de atrás para adelante (o sea, t está en el 0)
        while camino_lista[i] != S:
            p = camino_lista[i]
            q = camino_lista[i + 1]
            if not camino.es_backward(p):
                self.lados[q][p] -= e
            else:
                self.lados[p][q] += e
            i += 1
        self.flujo_max += e

    def flujo_maximal(self):
        return self.flujo_max


def _test():
    import doctest
    doctest.testmod()


if __name__ == '__main__':
    _test()
